package com.cjl.leetcodeWeeklyMatch;

import org.junit.jupiter.api.Test;

public class Match_368 {
    /**
     * 2908. 元素和最小的山形三元组 I
     *
     * @param nums
     * @return
     */
    public int minimumSum(int[] nums) {
        // 枚举每个元素右边最小值
        int len = nums.length;
        int[] sur = new int[len];
        // 初始化最后一项
        sur[len - 1] = nums[len - 1];
        // 递推计算sur中的每个值(至少要留前两位放置峰顶和左侧元素)
        for (int i = len - 2; i > 1; i--) {
            // 用前一个最小元素和当前的nums[i]比较获得新的最小值
            sur[i] = Math.min(sur[i + 1], nums[i]);
        }
        // 枚举每个元素左边的最小值
        int[] pre = new int[len];
        pre[0] = nums[0];
        for (int j = 1; j < len - 2; j++) {
            pre[j] = Math.min(pre[j - 1], nums[j]);
        }
        // 获取最小的三元组
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < len - 1; i++) {
            if (pre[i - 1] < nums[i] && nums[i] > sur[i + 1]) {
                res = Math.min(res, pre[i - 1] + nums[i] + sur[i + 1]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    @Test
    public void test() {
        int i = minimumSum(new int[]{8, 6, 1, 5, 3});
        System.out.println(i);
    }
}
